"""
动态规划。

设字符串 s 长度为 n ；
w(a, b)表示s的回文子串，a,b分别是其首尾字符在 s 中的位置；
W(b) 表示所有以第 b 个字符结尾的回文子串 w(x, b) (任意 x ) 组成的集合。

当 n = 1 时，即字符串s只有一个字符时，只有一个回文子串s，最长回文子串W(1)={s}。

当 n > 1 时，W(k)由s[k-1:k]（末尾单字符子串，必是回文串），s[k-2:k]（倒数两个字符组成的串）和W(k-1)决定。

- 第一个必是回文子串
- 第二个需要判断
- 第三个：对其中的每个子串w(x,k-1)，判断s[x-1]和s[k]是否相等。相等则说明s[x-1:k]在 W(k) 中

从第二个字符开始遍历；
使用两个数组分别存储当前循环和上一循环回文子串的起始下标；
每轮迭代后更新最长子串的首尾位置。

时间复杂度(n^2)
空间复杂度(n)
"""

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        n = len(s)
        p, q = [], []
        for i in range(1,n):
            for k in p+[i,i+1]:
                if k-1 >= 0 and s[k-1] == s[i]:
                    q.append(k-1)
            if i-q[0] > end-start: # q[0]是最左边界，i是最右边界，相当于不断扩展右边界，看左边界是否能扩展
                start, end = q[0], i
            p = q.copy()
            q.clear()
        return s[start:(end+1)]

if __name__ == '__main__':
    c = Solution()
    s = "abbd"
    print(c.longestPalindrome(s))